CD ROM Paradise Collection 4

home *** CD-ROM | disk | FTP | other *** search

/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / program / tjgold.zip / INSTALL.004 / FGUSER13.TXT < prev next >

Wrap

Text File | 1995-05-29 | 32KB | 805 lines

Single and Double Linked Lists "Time will run back and fetch the age of gold and speckled vanity will sicken soon and die." Milton Arrays Versus Lists Linked lists are invaluable and should form a strategic part of every programmer's arsenal. If you are not familiar with linked lists, you have probably been using arrays to meet your list management needs. But arrays have serious shortcomings. One-dimensional arrays provide a very quick and convenient way of managing lists. An array is a data structure designed to store data about a fixed number of identical elements. For example, the following variable could be used to store the addresses of my two sisters and three brothers: Addresses: array [1..5] of string Data in the array is accessed by specifying the element number. For example, the following statement would update my second sister's address: Addresses[2] := '38 The Ridgeway, Friern Barnet London' Arrays are very easy to create, but suffer from two major weaknesses: The size of the array is fixed at compile time. In other words, in your source code you must explicitly state the size (or bounds) of the array. In our simple example, this was not a problem because I only have 5 siblings. Imagine, however, that you need to write a generic name and address program. You don't know how many names and addresses will be required, but you must specify the number in your program. The typical solution is to choose a large number of elements (e.g. 200) and hope that the user doesn't need more. Not only does this impose a limit on the program's capacity, it also wastes memory if the maximum number of elements is not reached. Borland Pascal automatically allocates the memory for the entire array regardless of how many elements are actually used. Which leads to the second shortcoming. An individual data item must be 64k or less, and the entire array is considered to be an individual item. In our example, each element of the array is 256 bytes, so 256 of these elements would consume the entire 64k. In many cases arrays simply do not have the capacity to meet today's data needs. Linked lists do not suffer from these shortcomings. With a linked list, each element is stored independently. The first element includes a pointer indicating where the second element in the list is stored. The second element of the list includes a pointer to the third element in the list, and so on. When you reach an element in the list that points to NIL, you know you have reached the end of the list. You do not need to fix the maximum number of elements in the list at compile time. Furthermore, the data is stored on the heap (not in the data segment) and so is not limited to 64k. The list can use all available memory. The good news is that you do not need to understand all the details of how linked lists work. Gold takes care of all the internal list management mechanics. Single and Double Lists Gold offers singly and doubly linked lists. You need to understand a little list theory in order to decide which list type is appropriate for your application. A list is actually a collection of nodes. A node contains two primary elements: data, and one or two node pointers. The data is the information stored in the list, e.g. the names and addresses in the address book. The node pointer points to the adjacent node in the list, and provides a link between two nodes. In a single linked list, there is a single pointer at each node, which points to the next item in the list. If you are currently accessing the 100th node in the list and want to get the data from the 99th node, Gold would have to go all the way to the beginning of the list, find the pointer to the second node, go to the second node, find the pointer to the third node, go to the third node, and so on all the way to the 99th element. In a double linked list, there are two pointers at each node. One pointer points to the previous item in the list, and the other to the next item in the list. These are referred to as the next and prev pointers. In the previous example, Gold would just have to use the previous pointer to move to the 99th node in one step. Given this brief explanation of the two linked lists types, you might be wondering why anyone bothers with single linked lists since double linked lists are more powerful. The answer is two part: complexity and memory. Double linked lists are more complicated to manage than single linked lists, especially when inserting and deleting nodes. But, hey, you don't care because Gold hides all the complexity from you! Every node in a double linked list consumes 4 more bytes of memory (for the previous pointer) than the equivalent node in a single linked list. Although 4 bytes doesn't sound much, it can add up when you have several thousand nodes. If your lists will be short (say, 150 items or less) and you won't be going backwards along the list too often, use a single linked list. Otherwise, use a double linked list. The Three Linked List Types So far we have discussed two primary linked list types: single and double. Gold actually provides three different types of linked lists: two single linked lists and one double linked list. To create a linked list you must declare a variable of one of the following types: List Type Description StringLL This is a single linked list designed sepcifically for managing short lists of strings. These lists have a low code overhead and can only be used for storing strings. Behind the scenes, Gold uses this list type for managing menu items, and several other sets of small string lists such as the drive list in the PromptDir dialog. SingleLL A single linked list can be used for storing strings, records or binary data, and uses a single next pointer for node traversal. DoubleLL A double linked list can be used for storing strings, records or binary data, and uses a single next pointer for node traversal. List sorting is supported. The techniques for managing each of these list types are discussed in the following sections. In brief, all you do is declare a variable of the appropriate type (e.g. MyList: SingleLL), call an init procedure to initialize the variable, then call a series of add functions to add nodes to the list, and when you are finished with the list call the appropriate destroy procedure. Using StringLLs The StringLL is really the baby of the Gold's linked list family. It can only store strings and shouldn't be used to store more than forty (or so) elements, otherwise performance will suffer. Having said that, there are literally hundreds of situations where all you need is a list to manage several dozen strings. It might be simple, but it's very useful. Initializing the StringLL Before you can add items to (or populate) a StringLL it must, must, must be initialized using the procedure StrLLInit. For example: StrLLInit(MyList); All the names of procedures used to manipulate a StringLL list are prefixed with the characters "STRLL". Building the List Having initialized the list, you can add strings to the list using the following procedure: StrLLAdd(var SL:StringLL; Str:String): integer; Adds a new string node at the end of the passed StringLL. The function returns an integer indicating the success of the operation: a 0 indicates the item was successfully added and a 1 indicates failure (probably due to a lack of memory). There is no way to change data in StringLL, nor can you delete a node or insert a node. As McDonalds might say: "What you add is what you get"! If you need more list manipulation tools, switch to a SingleLL or DoubleLL. Getting String Data out of the List The following function is used to get a string from a linked list: StrLLGetStr(var SL:StringLL;Num:integer): string; The function is passed a StringLL and a (one-based) node number and returns the string stored at that node. Destroying the StringLL After you have finished with the list, always destroy the list, and in so doing free up the memory used to create the list with the following procedure: StrLLDone(var SL:StringLL); Frees the memory used by all the nodes in a StringLL. A StringLL Example Listed below is an extract of the DEMLNK1.PAS demo file which creates a StringLL and then displays the list contents using the PromptOKStrLL procedure. var I: integer; TextList: StringLL; begin I := 0; StrLLInit(TextList); inc(I,StrLLAdd(TextList,'Thank ...')); inc(I,StrLLAdd(TextList,'')); inc(I,StrLLAdd(TextList,'This ...')); inc(I,StrLLAdd(TextList,'of ...')); inc(I,StrLLAdd(TextList,'product to others.')); inc(I,StrLLAdd(TextList,'')); inc(I,StrLLAdd(TextList,'A ...')); inc(I,StrLLAdd(TextList,'in ...')); inc(I,StrLLAdd(TextList,'of the ....')); if I = 0 then {all's well} PromptOKStrLL(' Welcome ',TextList) else PromptOK(' Ouch! ',' Not enough memory'); StrLLDestroy(TextList); end. Notice the clever trick to avoid testing the return codes from the StrLLAdd function. "I" is incremented by the return code of each StrLLAdd call. If "I" is zero after all the calls, then every add operation must have been successful. The code make look a little strange, but it is a useful technique.Understanding Node Pointers To get the most from Gold's SingleLL and DoubleLL linked lists you need to have a modest understanding of node pointers. As you know, a linked list is a collection of nodes, with each node pointing to the next node in the list. To access the data stored at a node, you need to specify which node you want to access. This is done using a node pointer. For example, to change a string stored in a SingleLL you would use the function SLLChangeStr, and pass a pointer to the node along with the replacement string. If you wanted to change the string stored at the 20th node, for example, you will need to obtain a pointer to the node. Fortunately Gold includes the function SLLNodePtr expressly for this purpose. You pass a node number and the function returns a pointer to the node. The following code fragment shows how this might be implemented in a program: var SNP: SingleNodePtr; Result: integer; begin ... SNP := SLLNodePtr(20); Result := SLLChangeStr(SNP,'New string'); ... end. Alternatively, you could avoid the need for a variable and combine the two calls into one expression as follows: var Result: integer; begin ... Result := SLLChangeStr(SLLNodePtr(20),'New string'); ... end. Anywhere that a SingleNodePtr is required as a parameter, you can substitute the function SLLNodePtr. The examples (above) refer to single linked lists, but the same goes for double linked lists -- use the function DLLNodePtr to a return node pointer of type DoubleNodePtr. Using SingleLLs The SingleLL type is used to create a single linked list. Gold includes a generic set of routines for managing any data in a SingleLL. However, because many applications used linked lists to store strings, there is also a set of routines designed especially for single linked lists of strings. Initializing a SingleLL Variable A SingleLL variable must be initialized before data can be added to the list. There are two procedures for initializing SingleLLs: one for generic lists and one for string lists, as follows: InitSLL(var TheList:SingleLL); Initializes a single linked list and sets the list for storing any data. InitSLLStr(var TheList:SingleLL); Initializes a single linked list and sets the list for storing strings. The type SingleLL is declared in GOLDLINK as follows: SingleLL = record StartNodePtr: SingleNodePtr; EndNodePtr: SingleNodePtr; TotalNodes: longint; StrVars: boolean; Dirty: boolean; end; {SingleLL} Giving a SingleLL Focus Gold allows an application to have many linked lists active at the same time, i.e. two or more lists in the same scope. Gold needs to know which list to manipulate. Before calling the functions to add, modify and delete data in a list, you must instruct Gold to give a single linked list focus using the following procedure: SLLSetActiveList(var S:SingleLL); Instructs Gold to direct all single linked list management functions to the specified list. If you are managing multiple lists, you can use the procedure SLLActivatePrevList to change the focus back to the list which had focus prior to the last SLLSetActiveList call. Adding and Changing List Data Once a list has been given focus, you can use the following procedures and functions to add and modify the list data: SLLAdd(var TheData; Size:longint): integer; Adds data of any type to a new node at the end of a single linked list. The function is passed a variable, followed by a longint indicating the size of the variable. The function returns a 0 if successful. SLLInsertBefore(Node:SingleNodePtr;var TheData;Size:longint): integer; Inserts a new node in front of the node specified by the node pointer. The function returns a 0 if successful. SLLChange(Node:SingleNodePtr;var TheData;Size:longint): integer; Modifies the data stored at the specified node. The procedure is passed a pointer to the node where the new data will be stored, the data variable and the data size. The function returns a 0 if successful. SLLDelNode(Node:SingleNodePtr); Removes the specified node from the linked list. SLLGetNodeData(Node:SingleNodePtr;Var TheData); Retrieves the data at the specified node, and copies the contents into the specified variable. SLLGetNodeDataSize(Node:SingleNodePtr):longint; Returns the number of bytes of data stored at the specified node. Storing Records in a List Many of the SLL functions accept an untyped variable as one of the parameters. This allows the list to manage data of any type, e.g. integers, reals, records, enumerated types, etc. But ninety-nine percent of applications store either records or strings in linked lists. If you want to save a record in a node, just create a variable of the record's type, and then use the SLL add function to copy the record to a new node at the end of the list. For example, the following code stores a name and address at a node: type Location: record Name: string[20]; Address: string[50]; Zip: longint; end; {Location} var WorkAddress: Location AddressList: SingleLL; begin ... InitSLL(AddressList); SLLSetActiveList(AddressList); with WorkAddress do begin Name := 'Beavis'; Address := '1 Bonehead Park, Dallas TX'; Zip := 77665; end; SLLAdd(WorkAddress,sizeof(Address)); ... end. That's all there is to it. In a real application you might add hundreds of addresses to the list. Retrieving a record from the list is just as easy. The following statement will retrieve the twelfth address from the list: SLLGetNodeData(SLLNodePtr(12),WorkAddress); Storing Strings in a List If you have initialized the list using InitSLLStr (to store strings) then you should use the following functions to add, modify and access strings in the list: SLLAddStr(Str:string):integer; Adds a new node to the end of a single linked list and stores the string at the node. The function returns a 0 if successful. SLLInsStrBefore(Node:SingleNodePtr;Str:string): integer; Inserts a new node, prior to the node specified by the node pointer, and stores a string at the node. The function returns a 0 if successful. SLLChangeStr(Node:SingleNodePtr;Str:string): integer; Modifies the string stored at the specified node. The procedure is passed a pointer to the node where the new string will be stored, along with the string. The function returns a 0 if successful. SLLGetStr(Num:longint):string; Returns the string at the specified node number. Note (for convenience) that this function accepts a node number and not a node pointer. Populating a List from a File Gold makes it easy to save and restore lists from a text file using the following two procedures: SLLLoadFromFile(Filename:string):integer; Populates the active linked list from a text file. Each line of the text file is a node in the linked list. Any existing data in the active linked list is destroyed. The active linked list must be initialized as a string linked list. The function returns a zero if the read was successful. SLLSaveToFile(Filename:string):integer; Saves the contents of the active single linked list to a text file. Each node of the list is saved as a line of text in the file. The function returns a zero if the save was successful. An existing file of the same name will be overwritten. Settings and Getting Bits Every node in a SingleLL (and a DoubleLL for that matter) has a special byte used to store up to eight bit flags. These bit flags are numbered from 0 through 7 and bits 0 and 1 are reserved for Gold's use -- for item tagging and color separation in list windows (discussed in the next chapter). The remaining 6 bits, numbered 2 through 7, are available for use. The following two routines are used to manage these bits. SLLSetBit(Node:SingleNodePtr; BitPos:byte; On:boolean); Sets the bit at the specified node to TRUE or FALSE. SLLGetBit(Node:SingleNodePtr; BitPos:byte): boolean; Returns TRUE if the specified bit at the node is on, or FALSE if it is off. Destroying the List The nodes in a linked list are constructed on the heap and can consume significant amounts of memory. When the list is no longer required, always destroy the list and free the associated memory by calling the following procedure: SLLDestroy; Disposes of all the nodes in the active SingleLL and frees all the memory used by the list. Using DoubleLLs The DoubleLL type is used to create a doubly linked list. The Gold routines to manage double linked lists are similar to the ones for managing single linked lists, except that the procedure and function names begin with DLL instead of SLL. Listed below are the DoubleLL procedures and functions which behave in the same manner as their corresponding SLL functions discussed in the previous section: Initializing a DoubleLL variable InitDLL(var TheList:DoubleLL); InitDLLStr(var TheList:DoubleLL); Giving a DoubleLL Focus DLLSetActiveList(var D:DoubleLL); DLLActivatePrevList; Node Pointer Management DLLNodePtr(NodeNumber:longint): DoubleNodePtr; Adding and Changing List Data DLLAdd(var TheData;Size:longint): integer; DLLChange(Node:DoubleNodePtr;var TheData;Size:longint): integer; DLLInsertBefore(Node:DoubleNodePtr;var TheData;Size:longint): int DLLDelNode(Node:DoubleNodePtr); DLLGetNodeData(Node:DoubleNodePtr;Var TheData); DLLGetNodeDataSize(Node:DoubleNodePtr):longint; Storing Strings in a List DLLAddStr(Str:string):integer; DLLGetNodeStr(Node:DoubleNodePtr;Start,Finish: longint): string; DLLGetStr(Num:longint): string; Populating a List from a File DLLLoadFromFile(Filename:string):integer; DLLSaveToFile(Filename:string):integer; Settings and Getting Bits DLLSetBit(Node:DoubleNodePtr; BitPos:byte; On:boolean); DLLGetBit(Node:DoubleNodePtr; BitPos:byte): boolean; Destroying the List DLLDestroy; Defining a Custom String Function A DoubleLL can store any form of binary data. By default, Gold will convert this data to string format whenever the functions DLLGetStr or DLLGetNodeStr are called. When the data is binary, all Gold can do is assume the data represents characters, and move the data into a string format. Since you know the format of the data (such as a name and address record), and you can probably return a much more elegant string than this default function. Gold allows you to write your own "binary to string" function which will be used in place of Gold's default function. All you have to do is create a function following some specific rules and then call the procedure DLLAssignGetStrFunc to instruct Gold to call your function every time a binary to string conversion is required. For a procedure to be eligible as a get string function it must adhere to the following rules: The procedure must be declared as a far procedure at the root level. Refer to the section Understanding Hooks in chapter 3 for further information. The procedure must be declared with three passed parameters. The first parameter must be of type DoubleNodePtr, the second and third parameters of type longint -- these numbers represent the starting and ending characters to be returned. The following procedure declaration follows these rules: {$F+} function AddrStr(Node:DoubleNodePtr;Start,Finish: longint): string; {} begin AddStr := .... end; { AddrStr} {$F-} The following procedure is then called to instruct Gold to call your procedure to test whether two nodes are in the wrong order: DLLAssignStrFunc(Func:DLLGetStrFunc); Instructs Gold to call the specified function when getting node data in string format. Additional Node Management Functions Behind the scenes, a double linked list has a pointer called the ActiveNodePtr. This pointer is similar to a file cursor, in that it points to a node (or line, if you will) in the list. Whenever you need to access a node in the list, the ActiveNodePtr is set to point to that node. This can speed list management operations significantly because there is a high probability that the next node to be accessed will be adjacent to the active node pointer -- rather than traversing from one end of the list to get to the new node, Gold simply shifts one node from the ActiveNodePtr. In most applications you won't need to worry about the ActiveNodePtr. However, in addition to the standard node pointer function DLLNodePtr, you can use the following procedures to manipulate the ActiveNodePtr: DLLAdvance(Amount:longint); Moves the ActiveNodePtr Amount nodes down the list. DLLRetreat(Amount:longint); Moves the ActiveNodePtr Amount nodes up the list. DLLJump(NodeNumber:longint); Moves the ActiveNodePtr to the specified node number. DLLShiftActiveNode(NewNode: DoubleNodePtr; NodeNumber: longint); Sets the ActiveNodePtr and the ActiveNodeNumber to the specified values. DLLSwapNodes(Node1,Node2:DoubleNodePtr); Swaps the data stored at the two nodes. Additional Bit Management Functions In addition to the standard DLLSetBit and DLLGetBit functions, there are the following bit management functions: DLLGetTagState(Num:longint):boolean; Returns the value of the tag bit (which defaults to bit 0). This bit is set by the user in a list window when altering the tag state of the item. DLLDelAllStatus(BitPos:byte;On:boolean); Deletes all nodes in the list which have the specified bit set to the specified state. The demo file DEMLNK2.PAS illustrates many of the DoubleLL functions. List Sorting One fundamental advantage of DoubleLL lists is that the nodes can be sorted. Gold has a default sort function which tests the data stored at the node like a string, regardless of whether the data is actually a string. To sort the list, simply call the following procedure: DLLSort(SortID:shortint; Ascending:boolean); Sorts the list (i.e. reorders all the nodes) in ascending or descending order. The SortID is only relevant to custom sort procedures, and should be specified as zero for the default sort. If you are using the DoubleLL to store non-string data, you might want to incorporate your own sorting routines. For example, you might store names and address as records, and want to sort on the zip field. If you tend to panic at the thought of having to write a sort algorithm, fear not! At the heart of every sort algorithm is a simple test to compare whether two nodes are in the correct order. For example, is "Bean" before "Ainsbury"? If the response is FALSE, the sort function will swap the two nodes, and process with the next comparison. Gold allows you to use a custom function (or sort hook) to perform your own wrong order function. Whenever Gold needs to decide whether two nodes are in the wrong order, your custom function will be called. All you have to do is create a function following some specific rules and then call the procedure DLLAssignWrongOrderFunc to instruct Gold to call your function every time a node comparison is required. For a procedure to be eligible as a wrong order function it must adhere to the following rules: The procedure must be declared as a far procedure at the root level. Refer to the section Understanding Hooks in chapter 3 for further information. The procedure must be declared with four passed parameters. The first parameter must be of type shortint, the second and third parameters of type DoubleNodePtr variable, and the fourth parameter of type boolean. The following procedure declaration follows these rules: {$F+} function SortHook(SortID:shortint; Node1,Node2:DoubleNodePtr; Asc:boolean): boolean; {} begin ... end; { SortHook} {$F-} The following procedure is then called to instruct Gold to call your procedure to test whether two nodes are in the wrong order: DLLAssignWrongOrderFunc(Func:DLLWrongOrderFunc); Instructs Gold to call the specified function when sorting a double linked list. The first parameter passed to the wrong order function is the parameter which you used when calling the DLLSort function, and it is designed to allow you to sort a list in more than one way. The example below uses the SortID to decide which field of a record to sort on. The second and third parameters are pointers to the two nodes which are being sorted. The final parameter is a boolean indicating which order to sort the list: ascending or descending. The best way to explain the sorting concepts is by example. Let's assume the active double linked list has been used to store records of the following type: Location: record Name: string[20]; Address: string[50]; Zip: longint; end; {Location} The following function could be used to allow sorting on any one of the three fields based on the SortID. {$F+} function RecordSort(SortID:shortint; Node1,Node2:DoubleNodePtr; Asc:boolean): boolean; {} var P1,P2:pointer; begin P1 := Node1; P2 := Node2; case SortID of 1: begin if Asc then RecordSort := Location(P1^).Name > Location(P2^).Name else RecordSort := Location(P2^).Name > Location(P1^).Name; end; 2: begin if Asc then RecordSort := Location(P1^).Address > Location(P2^).Address else RecordSort := Location(P2^).Address > Location(P1^).Address; end; 3: begin if Asc then RecordSort := Location(P1^).Zip > Location(P2^).Zip else RecordSort := Location(P2^).Zip > Location(P1^).Zip; end; end; end; { RecordSort} {$F-} begin ... DLLAssignWrongOrderFunc(RecordSort); ... end. To sort the example list by name in ascending order you would make the following call: DLLSort(1,true); To sort the example list by zip in descending order you would make the following call: DLLSort(3,false);